Voir

Comparaison entre modèle actuel et brouillon[modifier | modifier le code]

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

Complexité en temps
Découvreurs ou inventeurs	Peter E. Hart, Nils John Nilsson, Bertram Raphael
Date de publication	1968
Problèmes liés	Algorithme de recherche, algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme de Dijkstra
À l'origine de	Jump point search
Pire cas
Pire cas

Complexité en temps
Découvreurs ou inventeurs	Peter E. Hart, Nils John Nilsson, Bertram Raphael
Date de publication	1968
Problèmes liés	Algorithme de recherche, algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme de Dijkstra
À l'origine de	Jump point search
Pire cas
Pire cas

Algorithme A*[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

nouveau modèle actuel[modifier | modifier le code]

RIPEMD[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

nouveau modèle actuel[modifier | modifier le code]

RIPEMD

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

RIPEMD-128[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

RIPEMD-128

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel[modifier | modifier le code]

RIPEMD-128

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

RIPEMD-160[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel[modifier | modifier le code]

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

RIPEMD-256[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

RIPEMD-256

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel[modifier | modifier le code]

RIPEMD-256

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

Médiane des médianes[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[1]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

nouveau modèle actuel[modifier | modifier le code]

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[1]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

Algorithme de Hopcroft-Karp[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

EdgeRank[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

nouveau modèle actuel[modifier | modifier le code]

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

Arbre de Van Emde Boas[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

nouveau modèle actuel[modifier | modifier le code]

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

Arbre B[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[2]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

nouveau modèle actuel[modifier | modifier le code]

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[2]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

Algorithme de Las Vegas[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Las Vegas

Les exécutions d'un algorithme de Las Vegas donnent toujours un résultat correct ; c'est le temps d'exécution qui est aléatoire.

Découvreur ou inventeur	László Babai
Date de découverte	1979^[3]
Problème lié	Paradigme algorithmique (en)
À l'origine de	Algorithme de Davis-Putnam

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log(n))$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Las Vegas

Les exécutions d'un algorithme de Las Vegas donnent toujours un résultat correct ; c'est le temps d'exécution qui est aléatoire.

Découvreur ou inventeur	László Babai
Date de découverte	1979^[3]
Problème lié	Paradigme algorithmique (en)
À l'origine de	Algorithme de Davis-Putnam

Complexité en temps
Pire cas	$O(n^{2})$
Meilleur cas	$O(n\log(n))$

Algorithme de Johnson[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

Algorithme d'Aho-Corasick[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme d'Aho-Corasick

exemple d'arbre préfixe (trie) généré dans l'application d'un algorithme d'Aho-Corasick

Découvreurs ou inventeurs	Alfred Aho, Margaret Corasick (d)
Date de découverte	1975^[4]
Problèmes liés	Exact string-matching algorithm (d), multiple string search algorithm (d)
À l'origine de	Algorithme de Commentz-Walter (en)

nouveau modèle actuel[modifier | modifier le code]

Algorithme d'Aho-Corasick

exemple d'arbre préfixe (trie) généré dans l'application d'un algorithme d'Aho-Corasick

Découvreurs ou inventeurs	Alfred Aho, Margaret Corasick (d)
Date de découverte	1975^[4]
Problèmes liés	Exact string-matching algorithm (d), multiple string search algorithm (d)
À l'origine de	Algorithme de Commentz-Walter (en)

Algorithme de Dijkstra[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Dijkstra

L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsqu'il a terminé avec les voisins.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1959^[5]
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), algorithme glouton, algorithme
Structure des données	Graphe
Basé sur	Algorithme de parcours en largeur
À l'origine de	Algorithme A*, link-state routing protocol (en), Open Shortest Path First, IS-IS

Complexité en temps
Pire cas	$O(\|E\|+\|V\|\log \|V\|)$ ^[6], $O(\|E\|+\|V\|\log \|V\|)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Dijkstra

L'algorithme de Dijkstra pour trouver le chemin le plus court entre a et b. Il choisit le sommet non visité avec la distance la plus faible, calcule la distance à travers lui à chaque voisin non visité, et met à jour la distance du voisin si elle est plus petite. Il marque le sommet visité (en rouge) lorsqu'il a terminé avec les voisins.

Découvreur ou inventeur	Edsger Dijkstra
Date de découverte	1959^[5]
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), algorithme glouton, algorithme
Structure des données	Graphe
Basé sur	Algorithme de parcours en largeur
À l'origine de	Algorithme A*, link-state routing protocol (en), Open Shortest Path First, IS-IS

Complexité en temps
Pire cas	$O(\|E\|+\|V\|\log \|V\|)$ ^[6], $O(\|E\|+\|V\|\log \|V\|)$

algorithme de Bellman-Ford[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Bellman-Ford

Découvreurs ou inventeurs	Richard Bellman (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), concept mathématique (en)
Structure des données	Graphe
À l'origine de	Routing Information Protocol^[7], Babel^[8]

Complexité en temps
Pire cas	$\Theta (\|V\|\|E\|)$
Meilleur cas	$\Theta (\|E\|)$

Complexité en espace
Pire cas	$\Theta (\|V\|)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Bellman-Ford

Découvreurs ou inventeurs	Richard Bellman (1958), L. R. Ford, Jr. (1956), Edward F. Moore (1957)
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d), concept mathématique (en)
Structure des données	Graphe
À l'origine de	Routing Information Protocol^[7], Babel^[8]

Complexité en temps
Pire cas	$\Theta (\|V\|\|E\|)$
Meilleur cas	$\Theta (\|E\|)$

Complexité en espace
Pire cas	$\Theta (\|V\|)$

Algorithme de Borůvka[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Borůvka

Animation représentant l'algorithme de Borůvka, dans la version sans contraction.

Découvreur ou inventeur	Otakar Borůvka
Date de publication	1926
Problèmes liés	Algorithme de la théorie des graphes (d), concept mathématique (en)

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Borůvka

Animation représentant l'algorithme de Borůvka, dans la version sans contraction.

Découvreur ou inventeur	Otakar Borůvka
Date de publication	1926
Problèmes liés	Algorithme de la théorie des graphes (d), concept mathématique (en)

algorithme de parcours en largeur[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de parcours en largeur

Ordre dans lequel les nœuds sont parcourus

Découvreur ou inventeur	Konrad Zuse
Date de découverte	1945
Problèmes liés	Uninformed search algorithm (d), parcours de graphe
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|+\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de parcours en largeur

Ordre dans lequel les nœuds sont parcourus

Découvreur ou inventeur	Konrad Zuse
Date de découverte	1945
Problèmes liés	Uninformed search algorithm (d), parcours de graphe
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|+\|E\|)=O(b^{d})$

Complexité en espace
Pire cas	$O(\|V\|)=O(b^{d})$

Algorithme de Floyd-Warshall[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Floyd-Warshall

Découvreur ou inventeur	Bernard Roy
Date de découverte	1959
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|n\|^{3})$
Moyenne	$O(\|V\|^{3})$
Meilleur cas	$O(\|V\|^{3})$

Complexité en espace
Pire cas	$O(\|V\|^{2})$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Floyd-Warshall

Découvreur ou inventeur	Bernard Roy
Date de découverte	1959
Problèmes liés	Algorithme de recherche de chemin (d), algorithme de la théorie des graphes (d)
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|n\|^{3})$
Moyenne	$O(\|V\|^{3})$
Meilleur cas	$O(\|V\|^{3})$

Complexité en espace
Pire cas	$O(\|V\|^{2})$

↑ ^{a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)
↑ ^{a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)
↑ ^{a et b} László Babai, « Monte-Carlo algorithms in graph isomorphism testing », [[Modèle:Article|{{Article}} : paramètre « titre » manquant, paramètre « périodique » manquant, paramètre « date » manquant]] : paramètre « périodique » manquant,‎ 1979
↑ ^{a et b} (en) Alfred V. Aho et Margaret J. Corasick, « Efficient string matching: an aid to bibliographic search », Communications of the ACM, New York, ACM, vol. 18, n^o 6,‎ 1^er juin 1975, p. 333-340 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/360825.360855)
↑ ^{a et b} (en) E. W. Dijkstra, « A note on two problems in connexion with graphs », Numerische Mathematik, Springer Science+Business Media, vol. 1, n^o 1,‎ décembre 1959, p. 269-271 (ISSN 0029-599X et 0945-3245, OCLC 1760917, DOI 10.1007/BF01386390, lire en ligne)
↑ ^{a et b} « http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf »
↑ ^{a et b} G. Malkin, RIP Version 2, (Request for comments), IETF, Novembre 1998, [lire en ligne], consulté le 28 mai 2022
↑ ^{a et b} J. Chroboczek, The Babel Routing Protocol, (Request for comments), IETF, Avril 2011, [lire en ligne], consulté le 28 mai 2022

[wikidata-8bfb307d4a12c04e302ae05e204046dea379a837Q55881151-1] {a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)

[wikidata-8b276371ef944464ae99b0d28d05e4f8c4a98c8dQ61783186-2] {a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)

[wikidata-e85a3db2503dd0cd0b9e769312655d15f9566734Q94972713-3] {a et b} László Babai, « Monte-Carlo algorithms in graph isomorphism testing », [[Modèle:Article|{{Article}} : paramètre « titre » manquant, paramètre « périodique » manquant, paramètre « date » manquant]] : paramètre « périodique » manquant,‎ 1979

[wikidata-82fe7c1b9186cbab57648736e8b3cbe36d934d5dQ55870932-4] {a et b} (en) Alfred V. Aho et Margaret J. Corasick, « Efficient string matching: an aid to bibliographic search », Communications of the ACM, New York, ACM, vol. 18, n^o 6,‎ 1^er juin 1975, p. 333-340 (ISSN 0001-0782 et 1557-7317, OCLC 1514517, DOI 10.1145/360825.360855)

[wikidata-79fa46f0eb95a8b1a259121600f393dd46f3bbe2Q21694527-5] {a et b} (en) E. W. Dijkstra, « A note on two problems in connexion with graphs », Numerische Mathematik, Springer Science+Business Media, vol. 1, n^o 1,‎ décembre 1959, p. 269-271 (ISSN 0029-599X et 0945-3245, OCLC 1760917, DOI 10.1007/BF01386390, lire en ligne)

[wikidata-d1c249ef5ef036159ce0fabf065af2a408384f46-6] {a et b} « http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.4349&rep=rep1&type=pdf »

[wikidata-ec379cded6912fb6057f342578c273d3467891d8Q47484547-7] {a et b} G. Malkin, RIP Version 2, (Request for comments), IETF, Novembre 1998, [lire en ligne], consulté le 28 mai 2022

[wikidata-736b9255e0ac9a8da82403f13659bc7cf8a0e75dQ47322975-8] {a et b} J. Chroboczek, The Babel Routing Protocol, (Request for comments), IETF, Avril 2011, [lire en ligne], consulté le 28 mai 2022

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]